【LeetCode 40】Combination Sum II 组合总和 II

发表于 | 分类于


“The Linux philosophy is “Laugh in the face of danger”.Oops.Wrong One. “Do it yourself”. Yes, that”s it.”
Linux的哲学就是“在危险面前放声大笑”，呵呵，不是这句，应该是“一切靠自己，自力更生”才对。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 *
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用一次。
 *
 * 先排序，再去重
 */
public class leetcode40 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        helper(candidates, target, 0, res, new ArrayList<>());
        return res;
    }

//    private void helper(int[] nums, int target, int pos, List<List<Integer>> res, List<Integer> bag) {
//        if (target == 0)
//            res.add(new ArrayList<>(bag));
//        if (target < 0)
//            return;
//        if (pos >= nums.length)
//            return;
//        else {
//            List<Integer> temp = new ArrayList<>(bag);
//            helper(nums, target, pos + 1, res, bag);
//            bag =temp;
//            bag.add(nums[pos]);
//            helper(nums, target - nums[pos], pos + 1, res, bag);
//        }
//
//    }

    private void helper(int[] nums, int target, int pos, List<List<Integer>> res, List<Integer> bag) {
        if (target == 0)
            res.add(new ArrayList<>(bag));
        if (target < 0)
            return;
        else {
            for (int i = pos; i < nums.length; i++) {
                //去重
                if (i > pos && nums[i] == nums[i - 1]) continue;
                bag.add(nums[i]);
                helper(nums, target-nums[i], i + 1, res, bag);
                bag.remove(bag.size() - 1);
            }
        }

    }

    public static void main(String []args) {
        new leetcode40().combinationSum2(new int []{10,1,2,7,6,1,5},  8);

    }
}
Thanks!